﻿// 107 出栈序列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using  namespace std;


/*
* http://oj.daimayuan.top/course/7/problem/114
* 
* 
现在有一个栈，有 n个元素，分别为 1,2,…,n。我们可以通过 push 和 pop 操作，
 将这 n个元素依次放入栈中，然后从栈中弹出，依次把出栈的元素写下来得到的序列就是出栈序列。

比如 n=3，如果执行 push 1, push 2, pop, push 3, pop, pop，那么我们 pop 操作得到的元素依次是 2,3,1。
也就是说出栈序列就是 2,3,1。

请按字典序从小到大的顺序输出所有的 n个元素的可行的出栈序列。

输入格式
一行一个整数 n。

输出格式
按字典序从小到大的顺序一行一行输出所有的 n个元素的可行的出栈序列，每行一个序列，相邻两个数字需要用空格隔开。

样例输入
3
样例输出
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
数据规模
对于 100%的数据，保证 1≤n≤12。
*/


int n;
vector<vector<int>> ans;


void dfs(int x, vector<int> v, stack<int>  st) {
	if (x > n) {
		while (!st.empty()) { v.push_back(st.top()), st.pop(); }
		ans.push_back(v);
		return;
	}
	vector<int> oriV = v;
	stack<int>  orist = st;

	orist.push(x);
	dfs(x + 1, oriV, orist);


	while (!st.empty()) {
		v.push_back(st.top()); st.pop();
		st.push(x);
		dfs(x + 1,v,st);
		st.pop();
	}



	return;
}


int main()
{
	scanf("%d",&n);
	vector<int> v; stack<int>  st;
	dfs(1,v,st);

	reverse(ans.begin(),ans.end());
	for (auto& ev : ans) {
		for (int i = 0; i < ev.size(); i++) {
			printf("%d ", ev[i])  ;
		}
		printf("\n");
	}

	return 0;
}

 